package com.lx.algorithm.code.xly3.class05;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2022-01-11 15:38:49
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2022-01-11     张李鑫                     1.0         1.0 Version
 */
public class Code03 {
    /**
     * 求完全二叉树节点的个数
     * <p>
     * 要求时间复杂度低于O(N)
     * todo:logN的没实现 先放着吧
     */

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static class Info {
        private int count;

        public Info(int count) {
            this.count = count;
        }
    }

    /**
     * log（n）二叉树的递归套路
     *
     * @param node
     * @return
     */
    public static int getNodeCount(Node node) {
        if (node == null) {
            return 0;
        }
        return process(node).count;

    }

    private static Info process(Node node) {
        if (node == null) {
            return new Info(0);
        }
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);
        return new Info(leftInfo.count + rightInfo.count + 1);
    }

    public static int nodeNum(Node head) {
        if (head == null) {
            return 0;
        }
        return bs(head, 1, mostLeftLevel(head, 1));
    }

    // node在第level层，h是总的深度（h永远不变，全局变量
    // 以node为头的完全二叉树，节点个数是多少
    public static int bs(Node node, int Level, int h) {
        if (Level == h) {
            return 1;
        }
        if (mostLeftLevel(node.right, Level + 1) == h) {
            return (1 << (h - Level)) + bs(node.right, Level + 1, h);
        } else {
            return (1 << (h - Level - 1)) + bs(node.left, Level + 1, h);
        }
    }

    // 如果node在第level层，
    // 求以node为头的子树，最大深度是多少
    // node为头的子树，一定是完全二叉树
    public static int mostLeftLevel(Node node, int level) {
        while (node != null) {
            level++;
            node = node.left;
        }
        return level - 1;
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        System.out.println(nodeNum(head));
        System.out.println(getNodeCount(head));

    }
}
